/**
 * 
 */
package edu.rit.checkers;

import java.util.ArrayList;
import java.util.List;

import edu.rit.pj.Comm;
import edu.rit.pj.ParallelRegion;
import edu.rit.pj.ParallelTeam;

/**
 * Use this class to run an SMP test on the Checkers problem
 * 
 * @author Ian Tewksbury (ict8574@rit.edu)
 */
public class CheckersSmp {
	/**
	 * used as a parameter for buildTree if thread count is specified
	 * by command line
	 */
	public static final int UNSPECIFIED_THREAD_COUNT = -1;
	
	/**
	 * The usage message for running this program
	 */
	private static final String USAGE =
		"usage: -Dpj.nt=<NT> CheckersSmp " +
		"<startDepth> <increaseDepth> <maxTime> <maxTimePerDepth>\n" +
		"<NT> is the number of parallel threads\n" +
		"<startDepth> the start depth of the tree\n" +
		"<increaseDepth> the amount to increase the depth " +
			"of the tree by if time allows\n" +
		"<maxTime> the max time to run the search\n" +
		"<depthMaxTime> the max time to spend searching " +
			"each depth increase\n";

	/**
	 * Run one Checkers SMP test based on given args
	 * 
	 * @param args
	 * 	args[0] <startDepth> the start depth of the tree
	 * 	args[1] <increaseDepth> the amount to increase the depth of the tree
	 *by if time allows
	 * 	args[2] <maxTime> the max time to run the search
	 * 	args[3] <maxTimePerDepth> the max time to spend searching
	 * 
	 * @throws Exception parallel stuff can throw Exceptions 
	 */
	public static void main(String[] args) throws Exception {
		//PJ init
		Comm.init(args);
		
		int[] parsedArgs = Helpers.parseArgs(args);
		
		if(parsedArgs != null) {
			CheckersSmp.runSmpTest(parsedArgs[0], parsedArgs[1], parsedArgs[2],
				parsedArgs[3], true, CheckersSmp.UNSPECIFIED_THREAD_COUNT);
		} else {
			System.out.println(USAGE);
		}
	}
	
	/**
	 * Run a SMP test based on the given parameters.  Grows a tree for the max
	 * amount of time and then does a final a-b on it.  Will print out info 
	 * about the tree before and after the final a-b if r
	 * 
	 * @param startDepth the start max depth of the tree
	 * @param depthIncrease the amount to increase the max depth by
	 * if time allows
	 * @param timeLimit the max time to search the tree for
	 * @param timeLimitForDepth the max time to search a specific max depth
	 * @param printInfo whether to print info about the tree
	 * @param numThreads the number of threads to run this SMP test with
	 * 
	 * @return the number of nodes explored while building the tree
	 * 
	 * @throws Exception parallel stuff can throw Exceptions 
	 */
	public static long runSmpTest(int startDepth, int depthIncrease,
			int timeLimit, int timeLimitForDepth,
			boolean printInfo, int numThreads) throws Exception {
		
		ConfigNode.resetNodeId();
		
		long tStart, tABStart;
		
		//get start time
		tStart = System.currentTimeMillis();
		
		//create logger
		Logger log = new Logger(System.out);
		log.loggerOn(printInfo);
		
		//build the tree
		log.println("SEARCH TREE");
		ConfigTree tree = null;
		tree = CheckersSmp.buildTree(startDepth, depthIncrease, timeLimit,
			timeLimitForDepth, numThreads);
		
		//print tree info and search time
		log.println(tree);
		log.println("Search Time: " +
			(System.currentTimeMillis() - tStart));
		
		//do a final alpha beta and print its running time
		log.println("\nFINAL ALPHA-BETA");
		tABStart = System.currentTimeMillis();
		tree.alphaBeta();
		log.println(tree);
		log.println("Final Alpha-Beta Time: " +
			(System.currentTimeMillis() - tABStart));
		
		//return total running time
		log.println("Total Time: " +
			(System.currentTimeMillis() - tStart));
		
		return tree.getAddedNodes();
	}
	
	/**
	 * This actually does the tree building using an SMP architecture.
	 * The root tree is grown until it has enough unexplored nodes to be
	 * given out to all of the treads.  Then each thread gets one unexplored
	 * node from the root tree and creates its own local tree to search using
	 * that unexplored node as its root.  Once the max time has been reached
	 * all of the threads quit and merge their child trees into the root tree.
	 * 
	 * @param startMaxDepth the starting max depth of the tree to grow
	 * @param depthIncreaseAmount the amount to increase the max depth by if
	 * there is time
	 * @param totalTimeLimit the max time to grow the tree for
	 * @param depthTimeLimit the max time to search a specific max depth of
	 * the tree
	 * @param numThreads the number of threads to explore the tree with
	 * 
	 * @return the tree that has been built based on the given parameters
	 * @throws Exception
	 */
	private static ConfigTree buildTree(
		final int startMaxDepth, final int depthIncreaseAmount,
		int totalTimeLimit, final int depthTimeLimit, int numThreads)
		throws Exception {
		
		//if thread count specified use that amount, otherwise leave it
		//	unspecified and it will be based on command line arguments
		ParallelTeam team = null;
		if(numThreads != UNSPECIFIED_THREAD_COUNT) {
			team = new ParallelTeam(numThreads);
		} else {
			team = new ParallelTeam();
		}
		
		ConfigNode root = new ConfigNode();
		final ConfigTree rootTree = new ConfigTree(startMaxDepth, root);
		rootTree.growTreeToSize(team.getThreadCount());
		
		final long stopTime = System.currentTimeMillis() + totalTimeLimit;
		final List<ConfigTree> childTrees = new ArrayList<ConfigTree>();

		team.execute(new ParallelRegion() {
			@Override
			public void run() throws Exception {
				//CACHE INTERFERENCE: avoidance
				//SOURCE: Taken from examples in Parallel Java Library
				@SuppressWarnings("unused")
				long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;
				@SuppressWarnings("unused")
				long pad8, pad9, pada, padb, padc, padd, pade, padf;
				
				ConfigNode localRoot;
				
				//the rootTree is a shared resource
				synchronized (rootTree) {
					localRoot = rootTree.getNextUnexploredNode();
				}
				
				//create the child tree from an unexplored node from the
				//	rootTree
				ConfigTree childTree =
					new ConfigTree((startMaxDepth+localRoot.depth), localRoot);
				
				//while there is time keep searching
				long localStopTime = stopTime;
				long localDeptTimeLimit = depthTimeLimit;
				int localDepthIncreaseAmount = depthIncreaseAmount;
				while(System.currentTimeMillis() < localStopTime) {
					//grow tree till either depth time reached or stop time
					//	reached
					long depthStopTime =
						System.currentTimeMillis() + localDeptTimeLimit;
					childTree.growTreeToCurrDepthLimit(
						Math.min(depthStopTime,localStopTime));
					
					//increase possible tree size
					childTree.increaseMaxDepth(localDepthIncreaseAmount);
				}
				
				//the child trees list are also a shared resource
				synchronized(childTrees) {
					childTrees.add(childTree);
				}
			}//END run
		});//END parallel region
	     
		//merge all of the trees from the different threads
		rootTree.mergChildTrees(childTrees);
		
		return rootTree;
	}
}
